/**
 * Given a binary tree, find the maximum path sum.
 * 
 * The path may start and end at any node in the tree.
 * For example:
 * Given the below binary tree,
 * 
 * 	   1
      / \
     2   3
 * 
 * Return 6
 * 
 * 
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int maxPathLength(TreeNode *root, int& max)
    {
        if(!root)
        {
            //max = max > root->val ? max : root->val;
            return 0;
        }
        if(!root->left && !root->right)
        {
            max = max > root->val ? max : root->val;
            return root->val;
        }
        
        int l,r;
        
        if(!root->left)
        {
            r = maxPathLength(root->right, max);
            max = max>r?max:r;
            max = max>root->val?max:root->val;
            max = max>r+root->val?max:r+root->val;
            int k = r + root->val > root->val? r+ root->val : root->val;
            return k;
        }
        
        if(!root->right)
        {
            l = maxPathLength(root->left, max);
            max = max>l?max:l;
            max = max>root->val?max:root->val;
            max = max>l+root->val?max:l+root->val;
            int k = l+root->val > root->val? l+root->val : root->val;
            return k;
        }
        
        l = maxPathLength(root->left, max);
        r = maxPathLength(root->right, max);
        int local = l + r + root->val;
        max = max>l?max:l;
        max = max>r?max:r;
        max = max>l+root->val?max:l+root->val;
        max = max>r+root->val?max:r+root->val;
        max = max>local?max:local;
        max = max>root->val?max:root->val;
        int k = l>r ? (l+root->val > root->val ? l+root->val : root->val) : (r+root->val > root->val ? r+root->val : root->val);
        return k;
    }

public:
    int maxPathSum(TreeNode *root)
    {
        if(root==NULL)
        return 0;
        
        int max=INT_MIN;
        maxPathLength(root, max);
        return max;

    }
};
